package q90_subsetsWithDup;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class Solution_1 {

    List<Integer> t = new ArrayList<Integer>();
    List<List<Integer>> ans = new ArrayList<List<Integer>>();
    public static void main(String[] args) {
        Solution_1 s = new Solution_1();
        System.out.println(s.subsetsWithDup(new int[]{1,2,2}));
    }

    public List<List<Integer>> subsetsWithDup(int[] nums) {
        Arrays.sort(nums);
        dfs(0, nums);
        return ans;
    }

    /**
     * 相较于子集 此题存在一个重复元素的限制
     * 通过画图也很容易直到，处理的方式是对于同一层的去重，那么递增子序列/全排列2的题来看
     * 可以发现同层的去重处理是直接在dfs内部的
     * 因此我们只需要在for循环的 *外部* 定义一个变量prev来记录上一个用的数字来处理本层的重复问题
     */
    public void dfs(int cur, int[] nums) {
        ans.add(new ArrayList<Integer>(t));

        if (cur >= nums.length){
            return;
        }
        // 同层去重
        int prev = 11;
        for (int i = cur; i < nums.length; i++) {
            if (nums[i] == prev){
                continue;
            }

            t.add(nums[i]);
            prev = nums[i];
            dfs(i + 1, nums);
            t.remove(t.size() - 1);
        }
    }
}
